package com.bm;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: BM100 设计LRU缓存结构
 *
 * @author weiruibai.vendor
 * Date: 2022/10/21 14:45
 */
public class BM100 {


    /**
     * eg1:["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2
     * <p>
     * 我们将缓存看成一个队列，最后一个参数为2代表capacity，所以
     * Solution s = new Solution(2);
     * s.set(1,1); //将(1,1)插入缓存，缓存是{"1"=1}，set操作返回"null"
     * s.set(2,2); //将(2,2)插入缓存，缓存是{"2"=2，"1"=1}，set操作返回"null"
     * output=s.get(1);// 因为get(1)操作，缓存更新，缓存是{"1"=1，"2"=2}，get操作返回"1"
     * s.set(3,3); //将(3,3)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"3"=3，"1"=1}，set操作返回"null"
     * output=s.get(2);// 因为get(2)操作，不存在对应的key，故get操作返回"-1"
     * s.set(4,4); //将(4,4)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"4"=4，"3"=3}，set操作返回"null"
     * output=s.get(1);// 因为get(1)操作，不存在对应的key，故get操作返回"-1"
     * output=s.get(3);//因为get(3)操作，缓存更新，缓存是{"3"=3，"4"=4}，get操作返回"3"
     * output=s.get(4);//因为get(4)操作，缓存更新，缓存是{"4"=4，"3"=3}，get操作返回"4"
     * <p>
     * eg2:["set","set","set","get","set","set","get"],[[1,1],[2,2],[3,3],[2],[4,4],[5,5],[2]],3
     * <p>
     * eg3:["set","set","get","set","get","set","get","get","get"],[[1,0],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2
     */

    public static void main(String[] args) {
        Solution solution = new Solution(2);
        /*solution.set(1, 1);
        solution.set(2, 2);
        System.out.println(solution.get(1));
        solution.set(3, 3);
        System.out.println(solution.get(2));
        solution.set(4, 4);
        System.out.println(solution.get(1));
        System.out.println(solution.get(3));
        System.out.println(solution.get(4));*/
        /*System.out.println("==================");
        solution = new Solution(3);
        solution.set(1, 1);
        solution.set(2, 2);
        solution.set(3, 3);
        System.out.println(solution.get(2));
        solution.set(4, 4);
        solution.set(5, 5);
        System.out.println(solution.get(2));*/
        solution = new Solution(2);
        solution.set(1, 0);
        solution.set(2, 2);
        System.out.println(solution.get(1));
        solution.set(3, 3);
        System.out.println(solution.get(2));
        solution.set(4, 4);
        System.out.println(solution.get(1));
        System.out.println(solution.get(3));
        System.out.println(solution.get(4));
    }
}

class Solution {
    private int capacity;
    private int curSize;
    private Map<Integer, DoubleLinkedNode> keyNode;// 通过key找节点

    private DoubleLinkedNode headNode;// 整体链表头节点（新）
    private DoubleLinkedNode tailNode;// 整体链表尾节点（旧）

    public Solution(int capacity) {
        this.capacity = capacity;
        keyNode = new HashMap<>();
    }

    public int get(int key) {
        int res = -1;
        DoubleLinkedNode node = keyNode.get(key);
        if (node != null) {
            res = node.value;
            readJustLinkedNode(node);
        }
        return res;
    }

    public void set(int key, int value) {
        DoubleLinkedNode node;
        if (keyNode.containsKey(key)) {
            // 包含，需要调整
            node = keyNode.get(key);
            node.value = value;
            keyNode.put(key, node);
            readJustLinkedNode(node);
        } else {
            // 新增
            node = new DoubleLinkedNode();
            node.key = key;
            node.value = value;
            keyNode.put(key, node);
            if (curSize == 0) {
                // 第一次
                headNode = tailNode = node;
                curSize++;
                return;
            }
            // 是否满了
            if (curSize == capacity) {
                keyNode.remove(tailNode.key);
                // 尾节点移动
                // 如果总量只有1
                if (capacity == 1) {
                    headNode = tailNode = node;
                    return;
                } else {
                    tailNode = tailNode.nextNode;
                    tailNode.lastNode = null;
                }
            } else {
                curSize++;
            }
            node.lastNode = headNode;
            headNode.nextNode = node;
            headNode = node;
        }
    }

    private void readJustLinkedNode(DoubleLinkedNode curNode) {
        // 移动到最前面
        // 1、如果当前只有一个节点就是自己或者是尾节点(不处理)
        if ((curNode.lastNode == null && curNode.nextNode == null) ||
                curNode == headNode) {
            return;
        } else if (curNode == tailNode) {
            // 2、node是末尾节点
            tailNode = curNode.nextNode;
            tailNode.lastNode = null;
            curNode.nextNode = null;
            headNode.nextNode = curNode;
            curNode.lastNode = headNode;
            headNode = curNode;
        } else {
            // 非首尾节点
            curNode.lastNode.nextNode = curNode.nextNode;
            curNode.nextNode.lastNode = curNode.lastNode;
            curNode.nextNode = null;
            curNode.lastNode = headNode;
            headNode.nextNode = curNode;
            headNode = curNode;
        }
    }


}

class DoubleLinkedNode {
    public int key;
    public int value;
    public DoubleLinkedNode lastNode;// 旧数据
    public DoubleLinkedNode nextNode;// 最新数据
}


